//implementation of list using linked list
//praneet sharma
//2010061
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<malloc.h>
#include<stdlib.h>

int len;

struct node{
	int value;
	struct node *next;
	};


struct node *add_to_list(struct node *first,int n) 
{
	struct node *new_node;
	new_node=malloc(sizeof(struct node));
	new_node->value=n;
	new_node->next=first;
	return new_node;
}


struct node *read_value()
{
	int a,num,mu;
	struct node *first=NULL;
	printf("how manuy values you want to enter:");
	scanf("%d",&len);
    printf("enter the values(from LSB to MSB):");
    for(mu=0;mu<=len-1;mu++)
    {
                            scanf("%d",&a);
                            first=add_to_list(first,a);
    }
    return first;
    
}



struct node *append_value(struct node *first,int n)
{
       struct node *prev;
       struct node *cur;
       struct node *app;
       app=malloc(sizeof(struct node));
       
       app->value=n;
       for(prev=NULL,cur=first;cur!=NULL;prev=cur,cur=cur->next)
       ;
       
       prev->next=app;
       app->next=cur;
       
      
       return first;
}



struct node *extend_list(struct node *first,struct node *sec)
{
       struct node *prev;
       struct node *cur;
        for(prev=NULL,cur=first;cur!=NULL;prev=cur,cur=cur->next)
        ;
        prev->next=sec;       
       return first;
} 
       
       

struct node *insert_value(struct node *first,int n,int m)
{
       struct node *prev;
       struct node *cur;
       struct node *ins;
       ins=malloc(sizeof(struct node));
       int count=0;
       for(prev=NULL,cur=first;count!=m && cur!=NULL;prev=cur,cur=cur->next)
       {
                                        count=count+1;
       }
       if(count+1>m)
       {
                   printf("position is not valid\n");
                   return first;
       }
       ins->value=n;
       if(prev==NULL)
       {
                     ins->next=cur;
                     first=ins;
       }
       else              
       {
                         prev->next=ins;
                         ins->next=cur;
       }
       return first;
}
       


	
	

struct node *remove_value(struct node *first,int n)
{
	struct node *prev;
	struct node *cur;
	for(prev=NULL,cur=first;cur!=NULL && cur->value!=n;prev=cur,cur=cur->next)
	;
	if(prev==NULL)
	{
		return first->next;
	}
	else
	{
		prev->next=cur->next;
	}
	free(cur);
	return first;
}



struct node *pop_value(struct node *first, int m)
{
       struct node *p1;
       struct node *p2;
       struct node *p3;
       struct node *cur;
       struct node *prev;
       int count=0;
       /*   case when the position is given as zero
       if(m==0)
       {
               for(p1=NULL,p2=first,p3=first->next;p3!=NULL;p1=p2,p2=p3,p3=p3->next)
               {
                                 p1->next=NULL;
                                 free(p2);
                                 //free(p3);
                                 return first;
               }
       } */                             
       for(prev=NULL,cur=first;count!=m && cur!=NULL;prev=cur,cur=cur->next)
       {
                                        count=count+1;
       }
       if(cur==NULL)
       {
                    return first;
       }
       if(prev==NULL)
       {
                    first=first->next;
       }
       else
       {
           prev->next=cur->next;
       }
       free(cur);
       return first;
}



int count_value(struct node *first, int n)
{
	int count=0;
	for(;first!=NULL;first=first->next)
	{
		if(first->value==n)
		{
			count=count+1;
		}
	}
	printf("the number of times the value %d is present in the list is %d \n",n,count);
}



int index_list(struct node *first, int n)
{
	int ind=0;
	for(;first!=NULL;first=first->next)
	{
		ind=ind+1;
		if(first->value==n)
		{
			break;
		}
	}
	printf("the index of the number %d is %d\n",n,ind);
}

//descending order sorting algorithm
struct node *sort_list(struct node *node1)
{
       printf("it will sort in descending order\n");
       struct node *so1;
       struct node *so2;
       int c;
       for(so1=node1;so1!=NULL;so1=so1->next)
       {
                                             for(so2=node1;so2!=NULL;so2=so2->next)
                                             {
                                                                                        if(so1->value>so2->value)
                                                                                        {
                                                                                                                 c=so1->value;
                                                                                                                 so1->value=so2->value;
                                                                                                                 so2->value=c;
                                                                                        }
                                             }
       }
       return node1;
                        
}

struct node *reverse_list(struct node *first)
{
        struct node *p;
        struct node *t;
        struct node *cur=NULL;
        for(p=first;p!=NULL;p=t)
       {
                                                            
                               t=p->next;
                               p->next=cur;
                               cur=p;
       }
       return cur;
}




int main()
{
	
	int a,choice,cou,pos,rem,ins,val,val_ins,l,ini,pos1,ap;
	char ch;
	struct node *node1;
	node1=read_value();
	struct node *first1;
	printf("numbers entered by you are : ");
	for(first1=node1;first1!=NULL;first1=first1->next)
	{
                                       printf("%d ",first1->value);
    }
    printf("\n");
	

	do{
		printf("-------------\n");
		printf("function list\n");
		printf("-------------\n");
		printf("1 to append\n");
		printf("2 to extend\n");
		printf("3 to insert\n");
		printf("4 to remove\n");
		printf("5 to pop\n");
		printf("6 to index\n");
		printf("7 to count\n");
		printf("8 to sort\n");
		printf("9 to reverse\n");
		printf("10 to exit\n");
		
		printf("enter your choice:");
		scanf("%d",&choice);
		switch(choice){
              
                 case 1:{
					printf("enter the value you want to append:");
					scanf("%d",&ap);	
					printf("\n");
					
					node1=append_value(node1,ap);
					struct node *p;
                    printf("values of node after insertion are : ");
					for(p=node1;p!=NULL;p=p->next)
					{
                                                  printf("%d ",p->value);
                    }        
                    printf("\n");          
                     break;
					} 
                
                case 2:{
                        struct node *node2;
                        node2=read_value();
	                    struct node *first2;
	                    printf("numbers entered by you are : ");
	                    for(first2=node2;first2!=NULL;first2=first2->next)
	                    {
                                        printf("%d ",first2->value);
                        }
                        printf("\n");
                        node1=extend_list(node1,node2);
                        struct node *p;
                        printf("values of node after insertion are : ");
					    for(p=node1;p!=NULL;p=p->next)
					    {
                                                  printf("%d ",p->value);
                         }                                     
                         printf("\n");          
                         break;
					    } 
                           
                          
				case 3:{
					printf("enter the value you want to insert:");
					scanf("%d",&ins);	
					printf("\n");
					printf("enter the position where you want to insert the value:");
					scanf("%d",&val_ins);
					node1=insert_value(node1,ins,val_ins);
					struct node *p;
                    printf("values of node after insertion are : ");
					for(p=node1;p!=NULL;p=p->next)
					{
                                                  printf("%d ",p->value);
                    }        
                    printf("\n");          
                     break;
					}
					
					
				case 4:{
					printf("enter the element you want to remove:");
					scanf("%d",&rem);
					node1=remove_value(node1,rem);
                    
                    struct node *p;
					printf("values of node are : ");
					for(p=node1;p!=NULL;p=p->next)
					{
                                                  printf("%d ",p->value);
                    }
					printf("\n");
					break;
					}
					
					
				case 5:{
                        printf("enter the position from where you want to pop the value:");
                        scanf("%d",&pos1);	
                        node1=pop_value(node1,pos1);
                        struct node *p;
					    printf("values of node after poping are : ");
					    for(p=node1;p!=NULL;p=p->next)
					    {
                                                   printf("%d ",p->value);
                        }
                        printf("\n");
                        break;
                       }
                       

				case 6:{
					printf("enter the number whose position you want to know:");
					scanf("%d",&pos);
					index_list(node1,pos);
					break;
					}
					
				
				case 7:{
					printf("enter the value you want to count : ");
					scanf("%d",&cou);
					count_value(node1,cou);
					break;
					}
					
			  case 8:{
                        node1=sort_list(node1);
                        struct node *p;
                        printf("values of node are : ");
					     for(p=node1;p!=NULL;p=p->next)
					     {
                                                  printf("%d ",p->value);
                         }
                         printf("\n");
                         break;
                     }
                        
                      
					
				case 9:{
                         node1=reverse_list(node1);
                         struct node *p;
					     printf("values of node are : ");
					     for(p=node1;p!=NULL;p=p->next)
					     {
                                                  printf("%d ",p->value);
                         }
                         break;
                         }
                         
                         
				case 10:{
                         return;
                         }
                         
				}
				
		setbuf(stdin,NULL);
		printf("enter y to continue and n to exit:");
		scanf("%c",&ch);

	}while(ch=='y'|ch=='Y');
	
 		

}
